package com.cube.share.base.collection;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author litb
 * @since 2023/3/7 15:31
 * <p>
 * LFU
 */
public class LFUCache<K, V> {

    private Map<K, CacheNode<K, V>> map;

    private CacheDeque<K, V>[] freqTable;

    private final int capacity;

    private int evictionCount;

    private int curSize = 0;

    private final ReentrantLock lock = new ReentrantLock();

    private static final int DEFAULT_INITIAL_CAPACITY = 1000;

    private static final float DEFAULT_EVICTION_FACTOR = 0.75f;

    public LFUCache(final int maxCapacity, final float evictionFactor) {
        if (maxCapacity <= 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    maxCapacity);
        }
        boolean factorInRange = evictionFactor <= 1 && evictionFactor > 0;
        if (!factorInRange || Float.isNaN(evictionFactor)) {
            throw new IllegalArgumentException("Illegal eviction factor value:"
                    + evictionFactor);
        }
        this.capacity = maxCapacity;
        this.evictionCount = (int) (capacity * evictionFactor);
        this.map = new HashMap<>();
        this.freqTable = new CacheDeque[capacity + 1];
        for (int i = 0; i <= capacity; i++) {
            freqTable[i] = new CacheDeque<>();
        }
        for (int i = 0; i < capacity; i++) {
            freqTable[i].nextDeque = freqTable[i + 1];
        }
        freqTable[capacity].nextDeque = freqTable[capacity];
    }


    static class CacheNode<K, V> {

        CacheNode<K, V> prev;
        CacheNode<K, V> next;
        K key;
        V value;
        CacheDeque<K, V> owner;

        CacheNode() {
        }

        CacheNode(final K key, final V value) {
            this.key = key;
            this.value = value;
        }

        static <K, V> CacheNode<K, V> withdrawNode(final CacheNode<K, V> node) {
            if (node != null && node.prev != null) {
                node.prev.next = node.next;
                if (node.next != null) {
                    node.next.prev = node.prev;
                }
            }
            return node;
        }
    }

    /**
     * 自定义LIFO 双端队列,允许将元素放在deque的顶部,并轮询最后添加的元素
     * <p>
     * 链表结构last = node = node ... first
     *
     * @param <K>
     * @param <V>
     */
    static class CacheDeque<K, V> {
        CacheNode<K, V> last;
        CacheNode<K, V> first;

        CacheDeque<K, V> nextDeque;

        CacheDeque() {
            last = new CacheNode<>();
            first = new CacheNode<>();
            last.next = first;
            first.prev = last;
        }

        /**
         * 将指定 key,value 代表的node 放到双端队列的末端
         *
         * @param key   key
         * @param value value
         * @return node
         */
        CacheNode<K, V> addLast(final K key, final V value) {
            CacheNode<K, V> node = new CacheNode<>(key, value);
            node.owner = this;
            node.next = last.next;
            node.prev = last;
            node.next.prev = node;
            last.next = node;
            return node;
        }

        CacheNode<K, V> addLastNode(final CacheNode<K, V> node) {
            node.owner = this;
            node.next = last.next;
            node.prev = last;
            node.next.prev = node;
            last.next = node;
            return node;
        }

        CacheNode<K, V> pollFirst() {
            CacheNode<K, V> node = null;
            if (first.prev != last) {
                node = first.prev;
                first.prev = node.prev;
                first.prev.next = first;
                node.prev = null;
                node.next = null;
            }
            return node;
        }

        boolean isEmpty() {
            return last.next == first;
        }
    }
}
